#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class Solution
{
public:
    vector<int> dailyTemperatures(vector<int>& temperatures)
    {
        int n = temperatures.size();
        vector<int> ans(n);
        stack<int> indices;
        for(int i = 0; i < n; ++i)
        {
            while(!indices.empty())
            {   
                int pre_index = indices.top();
                if(temperatures[i] <= temperatures[pre_index])
                {
                    break;
                }
                indices.pop();
                ans[pre_index] = i - pre_index;
            }
            indices.push(i);
        }
        return ans;
    }
};

int main()
{
    Solution s;
    vector<int> temperatures = {73, 74, 75, 71, 69, 72, 76, 73};
    vector<int> vec_;
    vec_ = s.dailyTemperatures(temperatures);
    for(auto v : vec_)
        cout << v << " ";
    cout << endl;
    return 0;
}